﻿#include<iostream>
using namespace std;
int Max(int x,int y)
{
	return x>y?x:y;
}
int MaxSubArray(int *array,int length)
{
	int* All=new int[length];
	int* Kaishi=new int[length];
	All[length-1]=array[length-1];//初始化
	Kaishi[length-1]=array[length-1];
	for (int i=length-2;i>=0;i--)//从后向前推
	{
		Kaishi[i]=Max(array[i],Kaishi[i+1]+array[i]);//以i开始的，最大子数组和
		All[i]=Max(Kaishi[i],All[i+1]);//i到N-1的最大子数组和
	}
	int ResultValue=All[0];
	delete[] Kaishi;
	delete[] All;

	return ResultValue;
}
int main()
{
	int A[]={1, -2, 3, 10, -4, 7, 2, -5};
	cout<<MaxSubArray(A,8);
	return 0;
}